The invention relates in general to a multiplier for obtaining the multiplication product of elements in a Galois Field, and more particularly to a multiplier which effectively yields the product of Galois Field elements by using a combination circuit implementation.
Conventionally, binary scales are utilized to store and read data in a computer. An 8-bit byte is taken as an example. The byte xe2x80x9c00000000xe2x80x9d represents the value 0, the byte xe2x80x9c00000001xe2x80x9d represents the value 1, and similarly, the byte xe2x80x9c11111111xe2x80x9d represents the value 255. Herein, the symbol F{2{circumflex over ( )}8} is used to represent the 8-bit binary field. In the field F{2{circumflex over ( )}8}, every element represents a byte which corresponds to a value in [0,255] respectively. Moreover, the 8-bit Galois Field is denoted by GF{2{circumflex over ( )}8}. Every byte in the field GF{2{circumflex over ( )}8} can be represented by a value in {0, xcex1, xcex1{circumflex over ( )}2, . . . , xcex1{circumflex over ( )}255}, respectively, wherein xcex1 is xe2x80x9c00000010xe2x80x9d.
The multiplication operation, denoted by xe2x80x9c*xe2x80x9d, of any byte A (a7,a6,a5,a4,a3,a2,a1, a0) in GF{2{circumflex over ( )}8} and xcex1 conventionally follows two steps. First, every bit bi (i=0xcx9c7) of the byte A should be first left-shifted for one bit. Then, according to the Equation (1), the product of A* xcex1 can be obtained.
A*xcex1=(a6,a5,a4,a3,a2,a1,a0,0)⊕(0,0,0,a7,a7,a7,0,a7)xe2x80x83xe2x80x83(1)
While any byte A (a7, a6, a5, a4, a3, a2, a1, a0) in GF{2{circumflex over ( )}8} is to be multiplied by xcex1, the multiplication, denoted by xe2x80x9c*xe2x80x9d, is performed as follows : every bit bi (i=0xcx9c7) in the byte A should be first left-shifted for one bit, and then according to the Equation (1), the value of A* xcex1 can be obtained.
The operator xe2x80x9c⊕xe2x80x9d in the Equation (1) is an Exclusive OR (XOR) logic operation.
The result of the above-mentioned multiplication as shown in Table 1 can be obtained, basing on the equation xcex1{circumflex over ( )}8=xcex1{circumflex over ( )}4⊕xcex1{circumflex over ( )}3⊕xcex1{circumflex over ( )}2⊕xcex1{circumflex over ( )}0. Consequently, it is to be understood that xcex1{circumflex over ( )}2 is xe2x80x9c00000100xe2x80x9d, . . . , xcex1{circumflex over ( )}7 is xe2x80x9c10000000xe2x80x9d, and xcex1{circumflex over ( )}8 is xe2x80x9c00001101xe2x80x9d.
When the most significant bit (MSB), b7, of the byte A is xe2x80x9c1xe2x80x9d, according to the Equation (1), the value of A*xcex1 is the result of (a6,a5,a4,a3,a2,a1,a0,0) ⊕ (0,0,0,0,1,1,0,1). Thus, xcex1{circumflex over ( )}9 is xe2x80x9c00111010xe2x80x9d, . . . , xcex1{circumflex over ( )}12 is xe2x80x9c11001101xe2x80x9d, xcex1{circumflex over ( )}13 is xe2x80x9c10000111xe2x80x9d, . . . , and accordingly, xcex1{circumflex over ( )}255 is xe2x80x9c00000001xe2x80x9d. The operation including the steps of left-shifting every bit by one bit and utilizing the XOR logic operation is called a xe2x80x9cshift operation.xe2x80x9d
It is demonstrated that each of the 256 values 0, xcex1, xcex1{circumflex over ( )}2, . . . , xcex1{circumflex over ( )}255, corresponds to each byte in [0,255], respectively.
Conventionally, the multiplication product of the two elements A, B in GF{2{circumflex over ( )}8} is obtained by first expressing the multiplier B(Bxe2x89xa00) in the form of xcex1{circumflex over ( )}n (n=1xe2x89xa0255). Time for finding the value n is assumed to be T. To obtain the product of A*B, the multiplicand A should be multiplied by xcex1 n times, and each time, the shift operation mentioned above has to be performed once. Therefore, to multiply A by xcex1 n times needs the shift operation to be applied n times. This shift operation takes about one period T. While the value of n is large, such as 250, the shift operation has to be performed 250 times, which takes at long as 250*T. Therefore, the time-consumption is high.
It is therefore a primary object of the invention to provide a multiplier for obtaining the product of elements in a Galois Field. By applying the features of elements in the Galois Field, and a combination circuit implementation in computer hardware, the product of the multiplication can be quickly obtained.
In order to accomplish the object of the invention, a multiplier for obtaining the product of elements in a Galois Field is proposed. The multiplier performs the multiplication of two n-bit elements A(an-1, an-2, . . . . , a3, a2, a1, a0) and B(bn-1, bn-2, . . . , b3, b2, b1, b0) in the Galois Field. Therefore, the product C=A*B=(cn-1,cn-2, . . . , c3, c2, c1, c0) is obtained, wherein nxe2x89xa71 and ai (i=0xcx9cn-1), bj(j=0xcx9cn-1), and ck(k=0xcx9cnxe2x88x921) are all binary bits. The multiplier includes an AND planer, that is, a circuit for performing an AND logic operation of every bit ai(i=0xcx9cnxe2x88x921) in A(an-1, an-2, . . . , a3, a2, a1, a0) and every bit bj(j=0xcx9cn-1) in B(bn-1, bn-2, . . . , b3, b2, b1, b0) to obtain (an-1bn-1, an-1bn-2, . . . , an-1b0, an-2bn-1, an-2bn-2, . . . . , an-2b0, a0bn-1, a0bn-2, . . . , a0b0). The multiplier further includes an XOR planer, that is, a circuit for performing an XOR logic operation of (an-1bn-1, an-1bn-2, . . . , an-1b0, an-2bn-1, an-2bn-2, . . . , an-2b0, a0bn-1, a0bn-2, . . . , a0b0) to obtain (cn-1, cn-2, . . . , c3, c2, c1, c0).
As n=8,
c0=b0a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6⊕b7a7;
c1=b0a1⊕b1a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b6a7⊕b7a6⊕b7a7;
c2=b0a2⊕b1a1⊕b2a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b5a7⊕b6a6⊕b7a5⊕b6a7⊕b7a6;
c3=b0a3⊕b1a2⊕b2a1⊕b3a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2 ⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5;
c4=b0a4⊕b1a3⊕b2a2⊕b3a1⊕b4a0⊕b1a7⊕b2a6⊕b3a5⊕b4a4⊕b5a3⊕b6a2⊕b7a1⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3⊕b7a7;
c5=b0a5⊕b1a4⊕b2a3⊕b3a2⊕b4a1⊕b5a0⊕b2a7⊕b3a6⊕b4a5⊕b5a4⊕b6a3⊕b7a2⊕b3a7⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b3a7⊕b4a6⊕b5a5⊕b6a4⊕b7a3;
c6=b0a6⊕b1a5⊕b2a4⊕b3a3⊕b4a2⊕b5a1⊕b6a0⊕b3a7⊕b4a6⊕b5a5 ⊕b6a4⊕b7a3⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5; and
c7=b0a7⊕b1a6⊕b2a5⊕b3a4⊕b4a3⊕b5a2⊕b6a1⊕b7a0⊕b6a7⊕b7a6 ⊕b4a7⊕b5a6⊕b6a5⊕b7a4⊕b5a7⊕b6a6⊕b7a5.
It is therefore another object of the invention to provide a multiplier for data decoding of an audio-video processor. The multiplier performs a multiplication operation of elements in the Galois Field. The multiplier includes a first combination circuit for performing an AND logic operation of the bits of the multipicand and the bits of multiplier to yield another set of bits. The multiplier further includes a second combination circuit, for performing an XOR logic operation of the bits outputted from the first combination circuit to yield the bits of the product.
It is therefore a further object of the invention to provide a multiplication methods of elements in a Galois Field. The method is used for data decoding in an audio-video processor. The method includes a step of performing an AND logic operation of the bits of the multiplicand and the bits of the multiplier to obtain another set of bits and a step of performing an XOR logic operation of the outputted bits to obtain the product.